package com.unionfind;

/**
 *
 * QU quick union
 * S size
 * @Author: tgy
 * @Date: 2020-10-20 10:46
 */
public class UnionFind_QU_S extends UnionFind_QU {

    private int[] sizes;


    public UnionFind_QU_S(int capacity) {
        super(capacity);
        sizes = new int[parents.length];

        for (int i = 0; i < sizes.length; i++) {

            sizes[i] = 1;
        }
    }

    @Override
    protected void assignParent(int pv1, int pv2) {

        /**
         * 数元素少的加在树元素多的上面
         */
        if (sizes[pv1] > sizes[pv2]) {

            parents[pv2] = pv1;
            sizes[pv1] += sizes[pv2];
        }else {

            parents[pv1] = pv2;
            sizes[pv2] += sizes[pv1];
        }
    }
}
